"""
具体过程参考书
时间复杂度和空间复杂度均为N，是以递归方式实现
left表示从左到右的指针；right表示从右到左的指针

利用函数traverse_print函数判断链表是否回文
“怎么做”
    从最右指针和最左指针比较是否相等，同时要求递归接收到的值res也传入res
    递归过程只是更新了right指针，需要人为的更新left指针
    返回res
“什么时候做”
    一般像这种看最小单元，都是从后续遍历开始
"""
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    
    def __init__(self):
        self.left = None

    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        self.left = head
        return self.reverse_print(head)

    def reverse_print(self, right):
        if right is None:
            return True
        
        res = self.reverse_print(right.next)
        res = res and (self.left.val == right.val)
        self.left = self.left.next
        return res

"""
时间复杂度N,空间复杂度1
1. 首先，使用快慢指针找到中间节点和尾节点，用于翻转链表做准备
    注意：快慢指针均从head开始
2. 然后，从slow开始翻转链表，开始比较回文链表
3. 最后，实现翻转链表的方法reverse，使用迭代方法
    创建三个指针：
        pre指针用于作为最后的翻转后的头部节点，初始化为None；最终到达莫为节点
        cur指针用于作为当前节点指针，初始化为head;最终到达none；
        next指针用于更新cur指针，最终到达none
    cur
"""
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):

    def reverse(self, head):
        pre = None
        cur = head

        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None:
            return True
        
        # 1    
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 2
        left = head
        right = self.reverse(slow)

        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True